<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>有趣的算法问题之字符串专辑 | Jin Tian</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  
  
  
  
  <meta name="description" content="本文介绍 有趣的算法问题之字符串专辑">
<meta property="og:type" content="article">
<meta property="og:title" content="有趣的算法问题之字符串专辑">
<meta property="og:url" content="http://yoursite.com/2017/09/06/有趣的算法问题之字符串专辑/index.html">
<meta property="og:site_name" content="Jin Tian">
<meta property="og:description" content="本文介绍 有趣的算法问题之字符串专辑">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2017-09-07T08:13:51.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="有趣的算法问题之字符串专辑">
<meta name="twitter:description" content="本文介绍 有趣的算法问题之字符串专辑">
  
    <link rel="alternate" href="/atom.xml" title="Jin Tian" type="application/atom+xml">
  

  

  <link rel="icon" href="/css/images/mylogo.jpg">
  <link rel="apple-touch-icon" href="/css/images/mylogo.jpg">
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link href="https://fonts.googleapis.com/css?family=Open+Sans|Montserrat:700" rel="stylesheet" type="text/css">
  <link href="https://fonts.googleapis.com/css?family=Roboto:400,300,300italic,400italic" rel="stylesheet" type="text/css">
  <link href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet">
  <style type="text/css">
    @font-face{font-family:futura-pt;src:url(https://use.typekit.net/af/9749f0/00000000000000000001008f/27/l?subset_id=2&fvd=n5) format("woff2");font-weight:500;font-style:normal;}
    @font-face{font-family:futura-pt;src:url(https://use.typekit.net/af/90cf9f/000000000000000000010091/27/l?subset_id=2&fvd=n7) format("woff2");font-weight:500;font-style:normal;}
    @font-face{font-family:futura-pt;src:url(https://use.typekit.net/af/8a5494/000000000000000000013365/27/l?subset_id=2&fvd=n4) format("woff2");font-weight:lighter;font-style:normal;}
    @font-face{font-family:futura-pt;src:url(https://use.typekit.net/af/d337d8/000000000000000000010095/27/l?subset_id=2&fvd=i4) format("woff2");font-weight:400;font-style:italic;}</style>
  <link rel="stylesheet" href="/css/style.css">

  <script src="/js/jquery-3.1.1.min.js"></script>
  <script src="/js/bootstrap.js"></script>

  <!-- Bootstrap core CSS -->
  <link rel="stylesheet" href="/css/bootstrap.css" >

  
    <link rel="stylesheet" href="/css/dialog.css">
  

  

  
    <link rel="stylesheet" href="/css/header-post.css" >
  

  
  
  
    <link rel="stylesheet" href="/css/vdonate.css" >
  

</head>



  <body data-spy="scroll" data-target="#toc" data-offset="50">


  
  <div id="container">
    <div id="wrap">
      
        <header>

    <div id="allheader" class="navbar navbar-default navbar-static-top" role="navigation">
        <div class="navbar-inner">
          
          <div class="container"> 
            <button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-collapse">
              <span class="sr-only">Toggle navigation</span>
              <span class="icon-bar"></span>
              <span class="icon-bar"></span>
              <span class="icon-bar"></span>
            </button>

            
              <a class="brand" style="
                 border-width: 0px;  margin-top: 0px;"  
                href="#" data-toggle="modal" data-target="#myModal" >
                  <img width="124px" height="124px" alt="Hike News" src="/css/images/mylogo.jpg">
              </a>
            
            
            <div class="navbar-collapse collapse">
              <ul class="hnav navbar-nav">
                
                  <li> <a class="main-nav-link" href="/">首页</a> </li>
                
                  <li> <a class="main-nav-link" href="/archives">归档</a> </li>
                
                  <li> <a class="main-nav-link" href="/categories">分类</a> </li>
                
                  <li> <a class="main-nav-link" href="/tags">标签</a> </li>
                
                  <li> <a class="main-nav-link" href="/about">关于</a> </li>
                
                  <li> <a class="main-nav-link" href="http://luoli-luoli.com/chat">chat</a> </li>
                
                  <li><div id="search-form-wrap">

    <form class="search-form">
        <input type="text" class="ins-search-input search-form-input" placeholder="" />
        <button type="submit" class="search-form-submit"></button>
    </form>
    <div class="ins-search">
    <div class="ins-search-mask"></div>
    <div class="ins-search-container">
        <div class="ins-input-wrapper">
            <input type="text" class="ins-search-input" placeholder="请输入关键词..." />
            <span class="ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
            UNTITLED: '(无标题)',
        },
        ROOT_URL: '/',
        CONTENT_URL: '/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>
<script src="/js/insight.js"></script>

</div></li>
            </div>
          </div>
                
      </div>
    </div>

</header>



      
            
      <div id="content" class="outer">
        
          <section id="main" style="float:none;"><article id="post-有趣的算法问题之字符串专辑" style="width: 75%; float:left;" class="article article-type-post" itemscope itemprop="blogPost" >
  <div id="articleInner" class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="thumb" class="article-title" itemprop="name">
      有趣的算法问题之字符串专辑
    </h1>
  

      </header>
    
    <div class="article-meta">
      
	<a href="/2017/09/06/有趣的算法问题之字符串专辑/" class="article-date">
	  <time datetime="2017-09-06T12:17:17.000Z" itemprop="datePublished">2017-09-06</time>
	</a>

      
    <a class="article-category-link" href="/categories/默认分类/">默认分类</a>

      
	<a class="article-views">
	<span id="busuanzi_container_page_pv">
		阅读量<span id="busuanzi_value_page_pv"></span>
	</span>
	</a>

    </div>
    <div class="article-entry" itemprop="articleBody">
      
        <p>本文介绍 有趣的算法问题之字符串专辑<br><a id="more"></a></p>
<h1 id="有趣的算法问题之字符串专辑"><a href="#有趣的算法问题之字符串专辑" class="headerlink" title="有趣的算法问题之字符串专辑"></a>有趣的算法问题之字符串专辑</h1><blockquote>
<p>本文由在当地较为英俊的男子金天大神原创，版权所有，欢迎转载，本文首发地址 <a href="https://jinfagang.github.io" target="_blank" rel="noopener">https://jinfagang.github.io</a> 。但请保留这段版权信息，多谢合作，有任何疑问欢迎通过微信联系我交流：<code>jintianiloveu</code></p>
</blockquote>
<h2 id="字符串问题"><a href="#字符串问题" class="headerlink" title="字符串问题"></a>字符串问题</h2><p>字符串问题真的是经常遇到啊，小到匹配字符串，计算字符串相似度，大到海量数据统计搜索查询次数。好像都有字符串的身影。接下来就抛出几个厉害一点的字符串问题：</p>
<p><strong>最长的无重复子字符串</strong><br>这个问题的思想跟求取子数组的最大和相似。说白了就是遍历字符串，一个一个遍历，维护一个maxNoRepeat的string，每次遍历添加到这个string里面去，根据HashTable判断是否在前面出现过，如果出现那么就放弃这个maxNoRepeat，同时将其复制给一个tempString，这个是我们要保存的记录前面一次的最长不重复子串，放弃当前的maxNoRepeat之后，再将重复的字符串出现的位置后面的那一个开始复制给maxNoRepeat，继续遍历。代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></div><div class="line"></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> Hash&#123;</div><div class="line">    <span class="keyword">char</span> c;</div><div class="line">    <span class="keyword">int</span> times;</div><div class="line">    <span class="keyword">int</span> lastPos;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="built_in">string</span> <span class="title">find_max_no_repeat</span><span class="params">(<span class="built_in">string</span> a)</span> </span>&#123;</div><div class="line">    <span class="built_in">string</span> maxNoRepeat = <span class="string">""</span>;</div><div class="line">    <span class="built_in">string</span> tmp = <span class="string">""</span>;</div><div class="line"></div><div class="line">    <span class="keyword">int</span> n = <span class="number">52</span>;</div><div class="line">    Hash *HashTable = <span class="keyword">new</span> Hash[n];</div><div class="line"></div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; a.size(); ++i) &#123;</div><div class="line">        <span class="comment">// according to current char, update hash table</span></div><div class="line">        <span class="keyword">int</span> pos = (<span class="keyword">bool</span>) <span class="built_in">islower</span>(a[i]) ? (a[i] - <span class="string">'a'</span>) : (a[i] - <span class="string">'A'</span> + n/<span class="number">2</span>);</div><div class="line">        <span class="keyword">if</span> (HashTable[pos].times == <span class="number">1</span>) &#123;</div><div class="line">            <span class="comment">// indicates a[i] exist</span></div><div class="line">            <span class="comment">// be care of substring usage, begin index and len</span></div><div class="line">            <span class="keyword">auto</span> lastPos = HashTable[pos].lastPos;</div><div class="line">            maxNoRepeat = a.substr(lastPos + <span class="number">1</span>, i - lastPos);</div><div class="line">            tmp = maxNoRepeat.size() &gt; tmp.size()? maxNoRepeat: tmp;</div><div class="line">            <span class="comment">// clear HashTable, all char before last pos in a will be clear</span></div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k &lt; HashTable[pos].lastPos; ++k) &#123;</div><div class="line">                <span class="keyword">int</span> tmpChar = a[k];</div><div class="line">                <span class="keyword">int</span> aPos = (<span class="keyword">bool</span>) <span class="built_in">islower</span>(tmpChar) ? (tmpChar - <span class="string">'a'</span>) : (tmpChar - <span class="string">'A'</span> + n/<span class="number">2</span>);</div><div class="line">                HashTable[aPos].lastPos = <span class="number">0</span>;</div><div class="line">                HashTable[aPos].times = <span class="number">0</span>;</div><div class="line">            &#125;</div><div class="line">            <span class="comment">// remember to update last pos</span></div><div class="line">            HashTable[pos].lastPos = i;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            maxNoRepeat += a[i];</div><div class="line">            <span class="built_in">cout</span> &lt;&lt; maxNoRepeat &lt;&lt; <span class="built_in">endl</span>;</div><div class="line"></div><div class="line">            HashTable[pos].times = <span class="number">1</span>;</div><div class="line">            HashTable[pos].lastPos = i;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    maxNoRepeat = maxNoRepeat.size() &gt; tmp.size()? maxNoRepeat: tmp;</div><div class="line">    <span class="keyword">return</span> maxNoRepeat;</div><div class="line">&#125;</div><div class="line"></div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></div><div class="line">&#123;</div><div class="line">    <span class="built_in">string</span> a = <span class="string">"hgieophtpuaopwhrguf"</span>;</div><div class="line">    <span class="built_in">cout</span> &lt;&lt; a &lt;&lt; <span class="built_in">endl</span>;</div><div class="line">    <span class="built_in">string</span> b = find_max_no_repeat(a);</div><div class="line">    <span class="built_in">cout</span> &lt;&lt; b &lt;&lt; <span class="built_in">endl</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>看上去这个简单吗？简单你妈，老子骂了一天你敢信？我曹，这么说吧，没有看任何参考，完全自己骂出来的。这个问题的思路非常简单，就是维护一个中间值，遍历一遍字符串，维护一个哈希表，这个哈希表就是查找下一个字符是否出现过，如果出现过，那么就对字符进行截取，从上一次出现的位置截取，同时把它复制给中间值。但是别忘了还要维护哈希表，维护就是把每一次新增的字符之前的也就是最近一次重复的统统归于零，与此同时要更新一下当前重复的上次的位置。如此便可破此题。<br>好吧，这是我写过最牛逼算法了，其实如果你直接手撸实现的话会有无数的坑，总结一下：</p>
<ol>
<li>维护HashTable的时候，我是直接delete []，然后new，试图全部抹掉重新来，发现尼玛不行，这一点没有考虑抽取全，当前的字符串子串的HashTable还是不能变；</li>
<li>HashTable找到一个重复元素时，要更新HashTable该元素的上一次位置，也就是当前位置，因为你重复之后你就需要截取字符，截取字符如果不改变当前重复字符的位置的话，还是上一次重复的位置，下一次截取就会出错。</li>
</ol>
<p>好了，坑已踩完。</p>

      
    </div>
    <footer class="article-footer">
      
        <div id="donation_div"></div>

<script src="/js/vdonate.js"></script>
<script>
var a = new Donate({
  title: '骚年，加个好友打赏一下啊，现在连泡面都吃不起了啊', // 可选参数，打赏标题
  btnText: '打赏支持', // 可选参数，打赏按钮文字
  el: document.getElementById('donation_div'),
  wechatImage: 'https://i.loli.net/2017/09/27/59cb048ba6838.jpeg',
  alipayImage: 'https://i.loli.net/2017/09/27/59cb049cd0951.jpeg'
});
</script>
      
      
        
	<div id="comment">
		<!-- 来必力City版安装代码 -->
		<div id="lv-container" data-id="city" data-uid="MTAyMC8zMDA5MC82NjQ1">
		<script type="text/javascript">
		   (function(d, s) {
		       var j, e = d.getElementsByTagName(s)[0];

		       if (typeof LivereTower === 'function') { return; }

		       j = d.createElement(s);
		       j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
		       j.async = true;

		       e.parentNode.insertBefore(j, e);
		   })(document, 'script');
		</script>
		<noscript>为正常使用来必力评论功能请激活JavaScript</noscript>
		</div>
		<!-- City版安装代码已完成 -->
	</div>



      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2017/09/27/universe的消息架构/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          universe的消息架构
        
      </div>
    </a>
  
  
    <a href="/2017/09/06/有趣的算法问题之真的有趣吗/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">有趣的算法问题之真的有趣吗</div>
    </a>
  
</nav>

  
</article>

<!-- Table of Contents -->

  <aside id="toc-sidebar">
    <div id="toc" class="toc-article">
    <strong class="toc-title">文章目录</strong>
    
        <ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#有趣的算法问题之字符串专辑"><span class="nav-number">1.</span> <span class="nav-text">有趣的算法问题之字符串专辑</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#字符串问题"><span class="nav-number">1.1.</span> <span class="nav-text">字符串问题</span></a></li></ol></li></ol>
    
    </div>
  </aside>
</section>
        
      </div>
      
      <footer id="footer">
  

  <div class="container">
      	<div class="row">
	      <p> Powered by <a href="http://www.luoli-luoli.com/" target="_blank">萝莉萝莉</a> and <a href="http://www.luoli-luoli.com/sia" target="_blank">Sia</a> </p>
	      <p id="copyRightEn">Copyright &copy; 2017 - 2018 Jin Tian All Rights Reserved.</p>
	      
	      
    		<p class="busuanzi_uv">
				访客数 : <span id="busuanzi_value_site_uv"></span> |  
				访问量 : <span id="busuanzi_value_site_pv"></span>
		    </p>
  		   
		</div>

		
  </div>
</footer>


<!-- min height -->

<script>
    var wrapdiv = document.getElementById("wrap");
    var contentdiv = document.getElementById("content");
    var allheader = document.getElementById("allheader");

    wrapdiv.style.minHeight = document.body.offsetHeight + "px";
    if (allheader != null) {
      contentdiv.style.minHeight = document.body.offsetHeight - allheader.offsetHeight - document.getElementById("footer").offsetHeight + "px";
    } else {
      contentdiv.style.minHeight = document.body.offsetHeight - document.getElementById("footer").offsetHeight + "px";
    }
</script>
    </div>
    <!-- <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
    <a href="/categories" class="mobile-nav-link">Categories</a>
  
    <a href="/tags" class="mobile-nav-link">Tags</a>
  
    <a href="/about" class="mobile-nav-link">About</a>
  
    <a href="http://luoli-luoli.com/chat" class="mobile-nav-link">Chat</a>
  
</nav> -->
    

<!-- mathjax config similar to math.stackexchange -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>

<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/scripts.js"></script>




  <script src="/js/dialog.js"></script>








	<div style="display: none;">
    <script src="https://s95.cnzz.com/z_stat.php?id=1260716016&web_id=1260716016" language="JavaScript"></script>
  </div>



	<script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js">
	</script>






  </div>

  <div class="modal fade" id="myModal" tabindex="-1" role="dialog" aria-labelledby="myModalLabel" aria-hidden="true" style="display: none;">
  <div class="modal-dialog">
    <div class="modal-content">
      <div class="modal-header">
        <h2 class="modal-title" id="myModalLabel">设置</h2>
      </div>
      <hr style="margin-top:0px; margin-bottom:0px; width:80%; border-top: 3px solid #000;">
      <hr style="margin-top:2px; margin-bottom:0px; width:80%; border-top: 1px solid #000;">


      <div class="modal-body">
          <div style="margin:6px;">
            <a data-toggle="collapse" data-parent="#accordion" href="#collapseOne" onclick="javascript:setFontSize();" aria-expanded="true" aria-controls="collapseOne">
              正文字号大小
            </a>
          </div>
          <div id="collapseOne" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingOne">
          <div class="panel-body">
            您已调整页面字体大小
          </div>
        </div>
      


          <div style="margin:6px;">
            <a data-toggle="collapse" data-parent="#accordion" href="#collapseTwo" onclick="javascript:setBackground();" aria-expanded="true" aria-controls="collapseTwo">
              夜间护眼模式
            </a>
        </div>
          <div id="collapseTwo" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingTwo">
          <div class="panel-body">
            夜间模式已经开启，再次单击按钮即可关闭 
          </div>
        </div>

        <div>
            <a data-toggle="collapse" data-parent="#accordion" href="#collapseThree" aria-expanded="true" aria-controls="collapseThree">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;关 于&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</a>
        </div>
         <div id="collapseThree" class="panel-collapse collapse" role="tabpanel" aria-labelledby="headingThree">
          <div class="panel-body">
            Jin Tian
          </div>
          <div class="panel-body">
            Copyright © 2018 Jintian All Rights Reserved.
          </div>
        </div>
      </div>


      <hr style="margin-top:0px; margin-bottom:0px; width:80%; border-top: 1px solid #000;">
      <hr style="margin-top:2px; margin-bottom:0px; width:80%; border-top: 3px solid #000;">
      <div class="modal-footer">
        <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
      </div>
    </div>
  </div>
</div>
  
  <a id="rocket" href="#top" class=""></a>
  <script type="text/javascript" src="/js/totop.js?v=1.0.0" async=""></script>
  
    <a id="menu-switch"><i class="fa fa-bars fa-lg"></i></a>
  
</body>
</html>